# -*- coding: utf-8 -*-
r"""
Finite lattices and semilattices

This module implements finite (semi)lattices. It defines:

.. csv-table::
    :class: contentstable
    :widths: 30, 70
    :delim: |

    :meth:`LatticePoset` | Construct a lattice.
    :meth:`MeetSemilattice` | Construct a meet semi-lattice.
    :meth:`JoinSemilattice` | Construct a join semi-lattice.
    :class:`FiniteLatticePoset` | A class for finite lattices.
    :class:`FiniteMeetSemilattice` | A class for finite meet semilattices.
    :class:`FiniteJoinSemilattice` | A class for finite join semilattices.

List of (semi)lattice methods
-----------------------------

**Meet and join**

.. csv-table::
    :class: contentstable
    :widths: 30, 70
    :delim: |

    :meth:`~FiniteMeetSemilattice.meet` | Return the meet of given elements.
    :meth:`~FiniteJoinSemilattice.join` | Return the join of given elements.
    :meth:`~FiniteMeetSemilattice.meet_matrix` | Return the matrix of meets of all elements of the meet semi-lattice.
    :meth:`~FiniteJoinSemilattice.join_matrix` | Return the matrix of joins of all elements of the join semi-lattice.

**Properties of the lattice**

.. csv-table::
    :class: contentstable
    :widths: 30, 70
    :delim: |

    :meth:`~FiniteLatticePoset.is_distributive` | Return ``True`` if the lattice is distributive.
    :meth:`~FiniteLatticePoset.is_modular` | Return ``True`` if the lattice is modular.
    :meth:`~FiniteLatticePoset.is_lower_semimodular` | Return ``True`` if the lattice is lower semimodular.
    :meth:`~FiniteLatticePoset.is_upper_semimodular` | Return ``True`` if the lattice is upper semimodular.
    :meth:`~FiniteLatticePoset.is_atomic` | Return ``True`` if every element of the lattice can be written as a join of atoms.
    :meth:`~FiniteLatticePoset.is_coatomic` | Return ``True`` if every element of the lattice can be written as a meet of coatoms.
    :meth:`~FiniteLatticePoset.is_geometric` | Return ``True`` if the lattice is atomic and upper semimodular.
    :meth:`~FiniteLatticePoset.is_complemented` | Return ``True`` if every element of the lattice has at least one complement.
    :meth:`~FiniteLatticePoset.is_relatively_complemented` | Return ``True`` if every interval of the lattice is complemented.
    :meth:`~FiniteLatticePoset.is_pseudocomplemented` | Return ``True`` if every element of the lattice has a pseudocomplement.
    :meth:`~FiniteLatticePoset.is_supersolvable` | Return ``True`` if the lattice is supersolvable.
    :meth:`~FiniteLatticePoset.is_planar` | Return ``True`` if the lattice has an upward planar drawing.
    :meth:`~FiniteLatticePoset.is_dismantlable` | Return ``True`` if the lattice is dismantlable.
    :meth:`~FiniteLatticePoset.breadth` | Return the breadth of the lattice.
    :meth:`~FiniteLatticePoset.is_vertically_decomposable` | Return ``True`` if the lattice is vertically decomposable.

**Elements and sublattices**

.. csv-table::
    :class: contentstable
    :widths: 30, 70
    :delim: |

    :meth:`~FiniteLatticePoset.atoms` | Return the list of elements covering the bottom element.
    :meth:`~FiniteLatticePoset.coatoms` | Return the list of elements covered by the top element.
    :meth:`~FiniteLatticePoset.double_irreducibles` | Return the list of double irreducible elements.
    :meth:`~FiniteLatticePoset.complements` | Return the list of complements of an element, or the dictionary of complements for all elements.
    :meth:`~FiniteMeetSemilattice.pseudocomplement` | Return the pseudocomplement of an element.
    :meth:`~FiniteLatticePoset.is_modular_element` | Return ``True`` if given element is modular in the lattice.
    :meth:`~FiniteLatticePoset.sublattice` | Return sublattice generated by list of elements.
    :meth:`~FiniteLatticePoset.maximal_sublattices` | Return maximal sublattices of the lattice.
    :meth:`~FiniteLatticePoset.frattini_sublattice` | Return the intersection of maximal sublattices of the lattice.
    :meth:`~FiniteLatticePoset.vertical_decomposition` | Return the vertical decomposition of the lattice.

**Miscellaneous**

.. csv-table::
    :class: contentstable
    :widths: 30, 70
    :delim: |

    :meth:`~FiniteLatticePoset.moebius_algebra` | Return the quantum Möbius algebra of the lattice.
    :meth:`~FiniteLatticePoset.quantum_moebius_algebra` | Return the quantum Möbius algebra of the lattice.
"""
#*****************************************************************************
#       Copyright (C) 2008 Peter Jipsen <jipsen@chapman.edu>,
#                          Franco Saliola <saliola@gmail.com>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************

from sage.categories.finite_lattice_posets import FiniteLatticePosets
from sage.combinat.posets.posets import Poset, FinitePoset
from sage.combinat.posets.elements import (LatticePosetElement,
                                           MeetSemilatticeElement,
                                           JoinSemilatticeElement)

####################################################################################

def MeetSemilattice(data=None, *args, **options):
    r"""
    Construct a meet semi-lattice from various forms of input data.

    INPUT:

    - ``data``, ``*args``, ``**options`` -- data and options that will
      be passed down to :func:`Poset` to construct a poset that is
      also a meet semilattice.

    .. seealso:: :func:`Poset`, :func:`JoinSemilattice`, :func:`LatticePoset`

    EXAMPLES:

    Using data that defines a poset::

          sage: MeetSemilattice([[1,2],[3],[3]])
          Finite meet-semilattice containing 4 elements

          sage: MeetSemilattice([[1,2],[3],[3]], cover_relations = True)
          Finite meet-semilattice containing 4 elements

    Using a previously constructed poset::

          sage: P = Poset([[1,2],[3],[3]])
          sage: L = MeetSemilattice(P); L
          Finite meet-semilattice containing 4 elements
          sage: type(L)
          <class 'sage.combinat.posets.lattices.FiniteMeetSemilattice_with_category'>

    If the data is not a lattice, then an error is raised::

          sage: elms = [1,2,3,4,5,6,7]
          sage: rels = [[1,2],[3,4],[4,5],[2,5]]
          sage: MeetSemilattice((elms, rels))
          Traceback (most recent call last):
          ...
          ValueError: Not a meet semilattice.
    """
    if isinstance(data,FiniteMeetSemilattice) and len(args) == 0 and len(options) == 0:
        return data
    P = Poset(data, *args, **options)
    if not P.is_meet_semilattice():
        raise ValueError("Not a meet semilattice.")
    return FiniteMeetSemilattice(P)

class FiniteMeetSemilattice(FinitePoset):
    """
    .. note::
        We assume that the argument passed to MeetSemilattice is the poset
        of a meet-semilattice (i.e. a poset with greatest lower bound for
        each pair of elements).

    TESTS::

        sage: M = MeetSemilattice([[1,2],[3],[3]])
        sage: TestSuite(M).run()

    ::

        sage: P = Poset([[1,2],[3],[3]])
        sage: M = MeetSemilattice(P)
        sage: TestSuite(M).run()

    """
    Element = MeetSemilatticeElement

    def _repr_(self):
        r"""
        TESTS::

            sage: M = MeetSemilattice([[1,2],[3],[3]])
            sage: M._repr_()
            'Finite meet-semilattice containing 4 elements'

        ::

            sage: P = Poset([[1,2],[3],[3]])
            sage: M = MeetSemilattice(P)
            sage: M._repr_()
            'Finite meet-semilattice containing 4 elements'
        """
        s  = "Finite meet-semilattice containing %s elements" %self._hasse_diagram.order()
        if self._with_linear_extension:
            s += " with distinguished linear extension"
        return s

    def meet_matrix(self):
        """
        Return a matrix whose ``(i,j)`` entry is ``k``, where
        ``self.linear_extension()[k]`` is the meet (greatest lower bound) of
        ``self.linear_extension()[i]`` and ``self.linear_extension()[j]``.

        EXAMPLES::

            sage: P = LatticePoset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False)
            sage: M = P.meet_matrix(); M
            [0 0 0 0 0 0 0 0]
            [0 1 0 1 0 0 0 1]
            [0 0 2 2 2 0 2 2]
            [0 1 2 3 2 0 2 3]
            [0 0 2 2 4 0 2 4]
            [0 0 0 0 0 5 5 5]
            [0 0 2 2 2 5 6 6]
            [0 1 2 3 4 5 6 7]
            sage: M[P(4).vertex,P(3).vertex] == P(0).vertex
            True
            sage: M[P(5).vertex,P(2).vertex] == P(2).vertex
            True
            sage: M[P(5).vertex,P(2).vertex] == P(5).vertex
            False
        """
        return self._hasse_diagram.meet_matrix()

    def meet(self, x, y=None):
        r"""
        Return the meet of given elements in the lattice.

        INPUT:

        -  ``x, y`` -- two elements of the (semi)lattice OR
        -  ``x`` -- a list or tuple of elements

        .. SEEALSO:: :meth:`sage.combinat.posets.lattices.FiniteJoinSemilattice.join()`.

        EXAMPLES::

            sage: D = Posets.DiamondPoset(5)
            sage: D.meet(1, 2)
            0
            sage: D.meet(1, 1)
            1
            sage: D.meet(1, 0)
            0
            sage: D.meet(1, 4)
            1

        Using list of elements as an argument. Meet of empty list is
        the bottom element::

            sage: B4=Posets.BooleanLattice(4)
            sage: B4.meet([3,5,6])
            0
            sage: B4.meet([])
            15

        For non-facade lattices operator ``*`` works for meet::

            sage: L = Posets.PentagonPoset(facade=False)
            sage: L(1)*L(2)
            0
        """
        if y is not None: # Handle basic case fast
            i, j = map(self._element_to_vertex, (x,y))
            return self._vertex_to_element(self._hasse_diagram._meet[i,j])
        m = self.cardinality()-1 # m = top element
        for i in (self._element_to_vertex(_) for _ in x):
            m = self._hasse_diagram._meet[i, m]
        return self._vertex_to_element(m)

    def pseudocomplement(self, element):
        """
        Return the pseudocomplement of ``element``, if it exists.

        The pseudocomplement is the greatest element whose
        meet with given element is the bottom element. I.e.
        in a meet-semilattice with bottom element `\hat{0}`
        the pseudocomplement of an element `e` is the element
        `e^\star` such that `e \wedge e^\star = \hat{0}` and
        `e' \le e^\star` if `e \wedge e' = \hat{0}`.

        See :wikipedia:`Pseudocomplement`.

        INPUT:

        - ``element`` -- an element of the lattice.

        OUTPUT:

        An element of the lattice or ``None`` if the pseudocomplement does
        not exist.

        EXAMPLES:

        The pseudocompelement's pseudocomplement is not always the original
        element::

            sage: L = LatticePoset({1: [2, 3], 2: [4], 3: [5], 4: [6], 5: [6]})
            sage: L.pseudocomplement(2)
            5
            sage: L.pseudocomplement(5)
            4

        An element can have complements but no pseudocomplement, or vice
        versa::

            sage: L = LatticePoset({0: [1, 2], 1: [3, 4, 5], 2: [5], 3: [6],
            ....:                   4: [6], 5: [6]})
            sage: L.complements(1), L.pseudocomplement(1)
            ([], 2)
            sage: L.complements(2), L.pseudocomplement(2)
            ([3, 4], None)

        .. SEEALSO:: :meth:`sage.combinat.posets.lattices.FiniteLatticePoset.is_pseudocomplemented()`.

        TESTS::

            sage: L = LatticePoset({'a': []})
            sage: L.pseudocomplement('a')
            'a'
            sage: L = LatticePoset({'a': ['b'], 'b': ['c']})
            sage: [L.pseudocomplement(e) for e in ['a', 'b', 'c']]
            ['c', 'a', 'a']
        """
        v = self._element_to_vertex(element)
        e = self._hasse_diagram.pseudocomplement(v)
        if e is None:
            return None
        return self._vertex_to_element(e)

####################################################################################

def JoinSemilattice(data=None, *args, **options):
    r"""
    Construct a join semi-lattice from various forms of input data.

    INPUT:

    - ``data``, ``*args``, ``**options`` -- data and options that will
      be passed down to :func:`Poset` to construct a poset that is
      also a join semilattice.

    .. seealso:: :func:`Poset`, :func:`MeetSemilattice`, :func:`LatticePoset`

    EXAMPLES:

    Using data that defines a poset::

          sage: JoinSemilattice([[1,2],[3],[3]])
          Finite join-semilattice containing 4 elements

          sage: JoinSemilattice([[1,2],[3],[3]], cover_relations = True)
          Finite join-semilattice containing 4 elements

    Using a previously constructed poset::

          sage: P = Poset([[1,2],[3],[3]])
          sage: J = JoinSemilattice(P); J
          Finite join-semilattice containing 4 elements
          sage: type(J)
          <class 'sage.combinat.posets.lattices.FiniteJoinSemilattice_with_category'>

    If the data is not a lattice, then an error is raised::

          sage: elms = [1,2,3,4,5,6,7]
          sage: rels = [[1,2],[3,4],[4,5],[2,5]]
          sage: JoinSemilattice((elms, rels))
          Traceback (most recent call last):
          ...
          ValueError: Not a join semilattice.
    """
    if isinstance(data,FiniteJoinSemilattice) and len(args) == 0 and len(options) == 0:
        return data
    P = Poset(data, *args, **options)
    if not P.is_join_semilattice():
        raise ValueError("Not a join semilattice.")
    return FiniteJoinSemilattice(P)

class FiniteJoinSemilattice(FinitePoset):
    """
    We assume that the argument passed to FiniteJoinSemilattice is the
    poset of a join-semilattice (i.e. a poset with least upper bound
    for each pair of elements).

    TESTS::

        sage: J = JoinSemilattice([[1,2],[3],[3]])
        sage: TestSuite(J).run()

    ::

        sage: P = Poset([[1,2],[3],[3]])
        sage: J = JoinSemilattice(P)
        sage: TestSuite(J).run()

    """
    Element = JoinSemilatticeElement

    def _repr_(self):
        r"""
        TESTS::

            sage: J = JoinSemilattice([[1,2],[3],[3]])
            sage: J._repr_()
            'Finite join-semilattice containing 4 elements'

        ::

            sage: P = Poset([[1,2],[3],[3]])
            sage: J = JoinSemilattice(P)
            sage: J._repr_()
            'Finite join-semilattice containing 4 elements'
        """
        s = "Finite join-semilattice containing %s elements"%self._hasse_diagram.order()
        if self._with_linear_extension:
            s += " with distinguished linear extension"
        return s

    def join_matrix(self):
        """
        Return a matrix whose ``(i,j)`` entry is ``k``, where
        ``self.linear_extension()[k]`` is the join (least upper bound) of
        ``self.linear_extension()[i]`` and ``self.linear_extension()[j]``.

        EXAMPLES::

            sage: P = LatticePoset([[1,3,2],[4],[4,5,6],[6],[7],[7],[7],[]], facade = False)
            sage: J = P.join_matrix(); J
            [0 1 2 3 4 5 6 7]
            [1 1 3 3 7 7 7 7]
            [2 3 2 3 4 6 6 7]
            [3 3 3 3 7 7 7 7]
            [4 7 4 7 4 7 7 7]
            [5 7 6 7 7 5 6 7]
            [6 7 6 7 7 6 6 7]
            [7 7 7 7 7 7 7 7]
            sage: J[P(4).vertex,P(3).vertex] == P(7).vertex
            True
            sage: J[P(5).vertex,P(2).vertex] == P(5).vertex
            True
            sage: J[P(5).vertex,P(2).vertex] == P(2).vertex
            False
        """
        return self._hasse_diagram.join_matrix()

    def join(self, x, y=None):
        r"""
        Return the join of given elements in the lattice.

        INPUT:

        -  ``x, y`` -- two elements of the (semi)lattice OR
        -  ``x`` -- a list or tuple of elements

        .. SEEALSO:: :meth:`sage.combinat.posets.lattices.FiniteMeetSemilattice.meet()`.

        EXAMPLES::

            sage: D = Posets.DiamondPoset(5)
            sage: D.join(1, 2)
            4
            sage: D.join(1, 1)
            1
            sage: D.join(1, 4)
            4
            sage: D.join(1, 0)
            1

        Using list of elements as an argument. Join of empty list is
        the bottom element::

            sage: B4=Posets.BooleanLattice(4)
            sage: B4.join([2,4,8])
            14
            sage: B4.join([])
            0

        For non-facade lattices operator ``+`` works for join::

            sage: L = Posets.PentagonPoset(facade=False)
            sage: L(1)+L(2)
            4
        """
        if y is not None: # Handle basic case fast
            i, j = map(self._element_to_vertex, (x,y))
            return self._vertex_to_element(self._hasse_diagram._join[i,j])
        j = 0 # j = bottom element
        for i in (self._element_to_vertex(_) for _ in x):
            j = self._hasse_diagram._join[i, j]
        return self._vertex_to_element(j)


####################################################################################

def LatticePoset(data=None, *args, **options):
    r"""
    Construct a lattice from various forms of input data.

    INPUT:

    - ``data``, ``*args``, ``**options`` -- data and options that will
      be passed down to :func:`Poset` to construct a poset that is
      also a lattice.

    OUTPUT:

        FiniteLatticePoset -- an instance of :class:`FiniteLatticePoset`

    .. seealso:: :class:`Posets`, :class:`FiniteLatticePosets`, :func:`JoinSemiLattice`, :func:`MeetSemiLattice`

    EXAMPLES:

    Using data that defines a poset::

        sage: LatticePoset([[1,2],[3],[3]])
        Finite lattice containing 4 elements

        sage: LatticePoset([[1,2],[3],[3]], cover_relations = True)
        Finite lattice containing 4 elements

    Using a previously constructed poset::

        sage: P = Poset([[1,2],[3],[3]])
        sage: L = LatticePoset(P); L
        Finite lattice containing 4 elements
        sage: type(L)
        <class 'sage.combinat.posets.lattices.FiniteLatticePoset_with_category'>

    If the data is not a lattice, then an error is raised::

        sage: elms = [1,2,3,4,5,6,7]
        sage: rels = [[1,2],[3,4],[4,5],[2,5]]
        sage: LatticePoset((elms, rels))
        Traceback (most recent call last):
        ...
        ValueError: Not a lattice.

    Creating a facade lattice::

        sage: L = LatticePoset([[1,2],[3],[3]], facade = True)
        sage: L.category()
        Join of Category of finite lattice posets and Category of finite enumerated sets and Category of facade sets
        sage: parent(L[0])
        Integer Ring
        sage: TestSuite(L).run(skip = ['_test_an_element']) # is_parent_of is not yet implemented

    """
    if isinstance(data,FiniteLatticePoset) and len(args) == 0 and len(options) == 0:
        return data
    P = Poset(data, *args, **options)
    if not P.is_lattice():
        raise ValueError("Not a lattice.")

    return FiniteLatticePoset(P, category = FiniteLatticePosets(), facade = P._is_facade)

class FiniteLatticePoset(FiniteMeetSemilattice, FiniteJoinSemilattice):
    """
    We assume that the argument passed to FiniteLatticePoset is the
    poset of a lattice (i.e. a poset with greatest lower bound and
    least upper bound for each pair of elements).

    TESTS::

        sage: L = LatticePoset([[1,2],[3],[3]])
        sage: TestSuite(L).run()

    ::

        sage: P = Poset([[1,2],[3],[3]])
        sage: L = LatticePoset(P)
        sage: TestSuite(L).run()

    """
    Element = LatticePosetElement

    def _repr_(self):
        r"""
        TESTS::

            sage: L = LatticePoset([[1,2],[3],[3]])
            sage: L._repr_()
            'Finite lattice containing 4 elements'

        ::

            sage: P = Poset([[1,2],[3],[3]])
            sage: L = LatticePoset(P)
            sage: L._repr_()
            'Finite lattice containing 4 elements'
        """
        s = "Finite lattice containing %s elements"%self._hasse_diagram.order()
        if self._with_linear_extension:
            s += " with distinguished linear extension"
        return s

    def atoms(self):
        """
        Return the atoms of this lattice.

        An *atom* of a lattice is an element covering the bottom element.

        .. SEEALSO::

            :meth:`coatoms`

        EXAMPLES::

            sage: L = Posets.DivisorLattice(60)
            sage: sorted(L.atoms())
            [2, 3, 5]

        TESTS::

            sage: LatticePoset().atoms()
            []
            sage: LatticePoset({0: []}).atoms()
            []
        """
        if self.cardinality() == 0:
            return []
        return self.upper_covers(self.bottom())

    def coatoms(self):
        """
        Return the co-atoms of this lattice.

        A *co-atom* of a lattice is an element covered by the top element.

        .. SEEALSO::

            :meth:`atoms`

        EXAMPLES::

            sage: L = Posets.DivisorLattice(60)
            sage: sorted(L.coatoms())
            [12, 20, 30]

        TESTS::

            sage: LatticePoset().coatoms()
            []
            sage: LatticePoset({0: []}).coatoms()
            []
        """
        if self.cardinality() == 0:
            return []
        return self.lower_covers(self.top())

    def double_irreducibles(self):
        """
        Return the list of double irreducible elements of this lattice.

        A *double irreducible* element of a lattice is an element
        covering and covered by exactly one element. In other words
        it is neither a meet nor a join of any elements.

        .. SEEALSO::

            :meth:`~sage.categories.finite_lattice_posets.FiniteLatticePosets.ParentMethods.meet_irreducibles`,
            :meth:`~sage.categories.finite_lattice_posets.FiniteLatticePosets.ParentMethods.join_irreducibles`

        EXAMPLES::

            sage: L = Posets.DivisorLattice(12)
            sage: sorted(L.double_irreducibles())
            [3, 4]

            sage: L = Posets.BooleanLattice(3)
            sage: L.double_irreducibles()
            []

        TESTS::

            sage: LatticePoset().double_irreducibles()
            []
            sage: Posets.ChainPoset(2).double_irreducibles()
            []
        """
        H = self._hasse_diagram
        return [self._vertex_to_element(e) for e in H
                if H.in_degree(e) == 1 and H.out_degree(e) == 1]

    def is_distributive(self):
        r"""
        Return ``True`` if the lattice is distributive, and ``False``
        otherwise.

        A lattice `(L, \vee, \wedge)` is distributive if meet
        distributes over join: `x \wedge (y \vee z) = (x \wedge y)
        \vee (x \wedge z)` for every `x,y,z \in L` just like `x \cdot
        (y+z)=x \cdot y + x \cdot z` in normal arithmetic. For duality
        in lattices it follows that then also join distributes over
        meet.

        EXAMPLES::

            sage: L = LatticePoset({0:[1,2],1:[3],2:[3]})
            sage: L.is_distributive()
            True
            sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]})
            sage: L.is_distributive()
            False
        """
        if self.cardinality() == 0: return True
        return (self.is_graded() and
         self.rank() == len(self.join_irreducibles()) ==
         len(self.meet_irreducibles()))

    def is_complemented(self):
        r"""
        Returns ``True`` if ``self`` is a complemented lattice, and
        ``False`` otherwise.

        EXAMPLES::

            sage: L = LatticePoset({0:[1,2,3],1:[4],2:[4],3:[4]})
            sage: L.is_complemented()
            True

            sage: L = LatticePoset({0:[1,2],1:[3],2:[3],3:[4]})
            sage: L.is_complemented()
            False
        """
        return self._hasse_diagram.is_complemented_lattice()

    def is_relatively_complemented(self):
        """
        Return ``True`` if the lattice is relatively complemented, and
        ``False`` otherwise.

        A lattice is relatively complemented if every interval of it
        is a complemented lattice.

        EXAMPLES::

            sage: L = LatticePoset({1: [2, 3, 4, 8], 2: [5, 6], 3: [5, 7],
            ....:                   4: [6, 7], 5: [9], 6: [9], 7: [9], 8: [9]})
            sage: L.is_relatively_complemented()
            True

            sage: L = Posets.PentagonPoset()
            sage: L.is_relatively_complemented()
            False

        Relatively complemented lattice must be both atomic and coatomic.
        Implication to other direction does not hold::

            sage: L = LatticePoset({0: [1, 2, 3, 4, 5], 1: [6, 7], 2: [6, 8],
            ....:                   3: [7, 8, 9], 4: [9, 11], 5: [9, 10],
            ....:                   6: [10, 11], 7: [12], 8: [12], 9: [12],
            ....:                   10: [12], 11: [12]})
            sage: L.is_atomic() and L.is_coatomic()
            True
            sage: L.is_relatively_complemented()
            False

        TESTS::

            sage: [Posets.ChainPoset(i).is_relatively_complemented() for
            ....:  i in range(5)]
            [True, True, True, False, False]

        Usually a lattice that is not relatively complemented contains elements
        `l`, `m`, and `u` such that `r(l) + 1 = r(m) = r(u) - 1`, where `r` is
        the rank function and `m` is the only element in the interval `[l, u]`.
        We construct an example where this does not hold::

            sage: B3 = Posets.BooleanLattice(3)
            sage: B5 = Posets.BooleanLattice(5)
            sage: B3 = B3.subposet([e for e in B3 if e not in [0, 7]])
            sage: B5 = B5.subposet([e for e in B5 if e not in [0, 31]])
            sage: B3 = B3.hasse_diagram()
            sage: B5 = B5.relabel(lambda x: x+10).hasse_diagram()
            sage: G = B3.union(B5)
            sage: G.add_edge(B3.sources()[0], B5.neighbors_in(B5.sinks()[0])[0])
            sage: L = LatticePoset(Poset(G).with_bounds())
            sage: L.is_relatively_complemented()
            False
        """
        from sage.misc.flatten import flatten
        from collections import Counter

        # Work directly with Hasse diagram
        H = self._hasse_diagram
        n = H.order()
        if n < 3:
            return True

        # Quick check: the lattice must be atomic and coatomic.
        if H.out_degree(0) != H.in_degree().count(1):
            return False
        if H.in_degree(n-1) != H.out_degree().count(1):
            return False

        for e1 in range(n-1):
            C = Counter(flatten([H.neighbors_out(e2) for e2 in H.neighbors_out(e1)]))
            if any(c == 1 and len(H.closed_interval(e1, e3)) == 3 for e3, c in C.iteritems()):
                return False
        return True

    def breadth(self, certificate=False):
        r"""
        Return the breadth of the lattice.

        The breadth of a lattice is the largest integer `n` such that
        any join of elements `x_1, x_2, \ldots, x_{n+1}` is join of a
        proper subset of `x_i`.

        This can be also characterized by sublattices: a lattice
        of breadth at least `n` contains a sublattice isomorphic to the
        Boolean lattice of `2^n` elements.

        INPUT:

        - ``certificate`` -- (boolean; default: ``False``) -- whether to
          return an integer (the breadth) or a certificate, i.e. a biggest
          set whose join differs from the join of any subset.

        EXAMPLES::

            sage: D10 = Posets.DiamondPoset(10)
            sage: D10.breadth()
            2

            sage: B3 = Posets.BooleanLattice(3)
            sage: B3.breadth()
            3
            sage: B3.breadth(certificate=True)
            [1, 2, 4]

        ALGORITHM:

        For a lattice to have breadth at least `n`, it must have an
        `n`-element antichain `A` with join `j`. Element `j` must
        cover at least `n` elements. There must also be `n-2` levels
        of elements between `A` and `j`.  So we start by searching
        elements that could be our `j` and then just check possible
        antichains `A`.

        TESTS::

            sage: Posets.ChainPoset(0).breadth()
            0
            sage: Posets.ChainPoset(1).breadth()
            1
        """
        # A place for optimization: Adding a doubly irreducible element to
        # a lattice does not change the breadth, except from 1 to 2.
        # Hence we could start by removing double irreducibles.

        from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets

        # First check if breadth is zero (empty lattice) or one (a chain).
        n = self.cardinality()
        if n == 0:
            return [] if certificate else 0
        if self.is_chain():
            return [self.bottom()] if certificate else 1
        # Breadth is at least two.

        # Work directly with the Hasse diagram
        H = self._hasse_diagram

        # Helper function: Join of elements in the list L.
        jn = H._join
        def join(L):
            j = 0
            for i in L:
                j = jn[i, j]
            return j

        indegs = [H.in_degree(i) for i in range(n)]
        max_breadth = max(indegs)

        for B in range(max_breadth, 1, -1):
            for j in H:
                if indegs[j] < B: continue

                # Get elements more than B levels below it.
                too_close = set(H.breadth_first_search(j,
                                                      neighbors=H.neighbors_in,
                                                      distance=B-2))
                elems = [e for e in H.order_ideal([j]) if e not in too_close]

                achains = PairwiseCompatibleSubsets(elems,
                                          lambda x,y: H.are_incomparable(x,y))
                achains_n = achains.elements_of_depth_iterator(B)

                for A in achains_n:
                    if join(A) == j:
                        if all(join(A[:i]+A[i+1:]) != j for i in range(B)):
                            if certificate:
                                return [self._vertex_to_element(e) for e in A]
                            else:
                                return B
        assert False, "BUG: breadth() in lattices.py have an error."

    def complements(self, element=None):
        r"""
        Return the list of complements of an element in the lattice,
        or the dictionary of complements for all elements.

        Elements `x` and `y` are complements if their meet and join
        are respectively the bottom and the top element of the lattice.

        INPUT:

        - ``element`` -- an element of the lattice whose complement is
          returned. If ``None`` (default) then dictionary of
          complements for all elements having at least one
          complement is returned.

        EXAMPLES::

            sage: L=LatticePoset({0:['a','b','c'], 'a':[1], 'b':[1], 'c':[1]})
            sage: C = L.complements()

        Let us check that `'a'` and `'b'` are complements of each other::

            sage: 'a' in C['b']
            True
            sage: 'b' in C['a']
            True

        Full list of complements::

            sage: L.complements() # random
            {0: [1], 1: [0], 'a': ['b', 'c'], 'b': ['c', 'a'], 'c': ['b', 'a']}

            sage: L=LatticePoset({0:[1,2],1:[3],2:[3],3:[4]})
            sage: L.complements() # random
            {0: [4], 4: [0]}
            sage: L.complements(1)
            []

        TESTS::

            sage: L=LatticePoset({0:['a','b','c'], 'a':[1], 'b':[1], 'c':[1]})
            sage: for v,v_complements in L.complements().items():
            ....:     for v_c in v_complements:
            ....:         assert L.meet(v,v_c) == L.bottom()
            ....:         assert L.join(v,v_c) == L.top()
        """
        if element is None:
            jn = self.join_matrix()
            mt = self.meet_matrix()
            n = self.cardinality()
            zero = 0
            one = n-1
            c = [[] for x in range(n)]
            for x in range(n):
                for y in range(x,n):
                    if jn[x][y]==one and mt[x][y]==zero:
                        c[x].append(y)
                        c[y].append(x)

            comps={}
            for i in range(n):
                if len(c[i]) > 0:
                    comps[self._vertex_to_element(i)] = (
                        [self._vertex_to_element(x) for x in c[i]] )
            return comps

        # Looking for complements of one element.
        if not element in self:
            raise ValueError("element (=%s) not in poset"%element)
        return [x for x in self if
         self.meet(x, element)==self.bottom() and
         self.join(x, element)==self.top()]

    def is_pseudocomplemented(self):
        """
        Return ``True`` if the lattice is pseudocomplemented, and ``False``
        otherwise.

        A lattice is pseudocomplemented if every element `e` has a
        pseudocomplement `e^\star`, i.e. the greatest element such that
        the meet of `e` and `e^\star` is the bottom element.

        See :wikipedia:`Pseudocomplement`.

        EXAMPLES::

            sage: L = LatticePoset({1: [2, 5], 2: [3, 6], 3: [4], 4: [7],
            ....:                   5: [6], 6: [7]})
            sage: L.is_pseudocomplemented()
            True

            sage: L = LatticePoset({1: [2, 3], 2: [4, 5, 6], 3: [6], 4: [7],
            ....:                   5: [7], 6: [7]})
            sage: L.is_pseudocomplemented()  # Element 3 has no pseudocomplement
            False

        .. SEEALSO:: :meth:`sage.combinat.posets.lattices.FiniteMeetSemilattice.pseudocomplement()`.

        TESTS::

            sage: LatticePoset({}).is_pseudocomplemented()
            True
        """
        H = self._hasse_diagram
        return all(H.pseudocomplement(e) is not None for e in H)

    def is_atomic(self):
        r"""
        Return ``True`` if the lattice is atomic, and ``False`` otherwise.

        A lattice is atomic if every element can be written as a join of atoms.

        EXAMPLES::

            sage: L = LatticePoset({1: [2, 3, 4], 2: [5], 3:[5], 4:[6], 5:[6]})
            sage: L.is_atomic()
            True

            sage: L = LatticePoset({0: [1, 2], 1: [3], 2: [3], 3:[4]})
            sage: L.is_atomic()
            False

        TESTS::

            sage: LatticePoset({}).is_atomic()
            True

        NOTES:

        See [Sta97]_, Section 3.3 for a discussion of atomic lattices.

        REFERENCES:

        .. [Sta97] Stanley, Richard.
           Enumerative Combinatorics, Vol. 1.
           Cambridge University Press, 1997

        .. SEEALSO::

            :meth:`~FiniteLatticePoset.is_coatomic`
        """
        return (self.cardinality() == 0 or
                self._hasse_diagram.out_degree(0) ==
                self._hasse_diagram.in_degree().count(1))

    def is_coatomic(self):
        r"""
        Return ``True`` if the lattice is coatomic, and ``False`` otherwise.

        A lattice is coatomic if every element can be written as a meet
        of coatoms; i.e. if the dual of the lattice is atomic.

        EXAMPLES::

            sage: L = Posets.BooleanLattice(3)
            sage: L.is_coatomic()
            True

            sage: L = LatticePoset({1: [2], 2: [3, 4], 3: [5], 4:[5]})
            sage: L.is_coatomic()
            False

        TESTS::

            sage: LatticePoset({}).is_coatomic()
            True

        .. SEEALSO::

            :meth:`~FiniteLatticePoset.is_atomic`
        """
        n = self.cardinality()
        if n == 0:
            return True
        return (self._hasse_diagram.in_degree(n-1) ==
                self._hasse_diagram.out_degree().count(1))

    def is_geometric(self):
        """
        Return ``True`` if the lattice is geometric, and ``False`` otherwise.

        A lattice is geometric if it is both atomic and upper semimodular.

        EXAMPLES:

        Canonical example is the lattice of partitions of finite set
        ordered by refinement::

            sage: S = SetPartitions(3)
            sage: L = LatticePoset( (S, lambda a, b: S.is_less_than(a, b)) )
            sage: L.is_geometric()
            True

        Smallest example of geometric lattice that is not modular::

            sage: L = LatticePoset(DiGraph('K]?@g@S?q?M?@?@?@?@?@?@??'))
            sage: L.is_geometric()
            True
            sage: L.is_modular()
            False

        Two non-examples::

            sage: L = LatticePoset({1:[2, 3, 4], 2:[5, 6], 3:[5], 4:[6], 5:[7], 6:[7]})
            sage: L.is_geometric()  # Graded, but not upper semimodular
            False
            sage: L = Posets.ChainPoset(3)
            sage: L.is_geometric()  # Modular, but not atomic
            False

        TESTS::

            sage: LatticePoset({}).is_geometric()
            True
            sage: LatticePoset({1:[]}).is_geometric()
            True
        """
        return self.is_atomic() and self.is_upper_semimodular()

    def is_planar(self):
        r"""
        Return ``True`` if the lattice is *upward* planar, and ``False``
        otherwise.

        A lattice is upward planar if its Hasse diagram has a planar drawing in
        the `\mathbb{R}^2` plane, in such a way that `x` is strictly below `y`
        (on the vertical axis) whenever `x<y` in the lattice.

        Note that the scientific litterature on posets often omits "upward" and
        shortens it to "planar lattice" (e.g. [GW14]_), which can cause
        confusion with the notion of graph planarity in graph theory.

        .. NOTE::

            Not all lattices which are planar -- in the sense of graph planarity
            -- admit such a planar drawing (see example below).

        ALGORITHM:

        Using the result from [Platt76]_, this method returns its result by
        testing that the Hasse diagram of the lattice is planar (in the sense of
        graph theory) when an edge is added between the top and bottom elements.

        EXAMPLES:

        The Boolean lattice of `2^3` elements is not upward planar, even if
        it's covering relations graph is planar::

            sage: B3 = Posets.BooleanLattice(3)
            sage: B3.is_planar()
            False
            sage: G = B3.cover_relations_graph()
            sage: G.is_planar()
            True

        Ordinal product of planar lattices is obviously planar. Same does
        not apply to Cartesian products::

            sage: P = Posets.PentagonPoset()
            sage: Pc = P.product(P)
            sage: Po = P.ordinal_product(P)
            sage: Pc.is_planar()
            False
            sage: Po.is_planar()
            True

        TESTS::

            sage: Posets.ChainPoset(0).is_planar()
            True
            sage: Posets.ChainPoset(1).is_planar()
            True

        REFERENCES:

        .. [GW14] \G. Gratzer and F. Wehrung,
           Lattice Theory: Special Topics and Applications Vol. 1,
           Springer, 2014.

        .. [Platt76] \C. R. Platt,
           Planar lattices and planar graphs,
           Journal of Combinatorial Theory Series B,
           Vol 21, no. 1 (1976): 30-39.

        """
        # The 8-element Boolean lattice is the smallest non-planar lattice.
        if self.cardinality() < 8:
            return True
        g = self._hasse_diagram.copy(immutable=False)
        g.add_edge(0, self.cardinality()-1)
        return g.is_planar()

    def is_modular(self, L=None):
        r"""
        Return ``True`` if the lattice is modular and ``False`` otherwise.

        Using the parameter ``L``, this can also be used to check that
        some subset of elements are all modular.

        INPUT:

        - ``L`` -- (default: ``None``) a list of elements to check being
          modular, if ``L`` is ``None``, then this checks the entire lattice

        An element `x` in a lattice `L` is *modular* if `x \leq b` implies

        .. MATH::

            x \vee (a \wedge b) = (x \vee a) \wedge b

        for every `a, b \in L`. We say `L` is modular if `x` is modular
        for all `x \in L`. There are other equivalent definitions,
        see :wikipedia:`Modular_lattice`.

        .. SEEALSO::

            :meth:`is_upper_semimodular`, :meth:`is_lower_semimodular`
            and :meth:`is_modular_element`

        EXAMPLES::

            sage: L = posets.DiamondPoset(5)
            sage: L.is_modular()
            True

            sage: L = posets.PentagonPoset()
            sage: L.is_modular()
            False

            sage: L = posets.ChainPoset(6)
            sage: L.is_modular()
            True

            sage: L = LatticePoset({1:[2,3],2:[4,5],3:[5,6],4:[7],5:[7],6:[7]})
            sage: L.is_modular()
            False
            sage: [L.is_modular([x]) for x in L]
            [True, True, False, True, True, False, True]

        ALGORITHM:

        Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1]_.
        """
        if not self.is_ranked():
            return False
        H = self._hasse_diagram
        n = H.order()
        if L is None:
            return all(H._rank[a] + H._rank[b] ==
                       H._rank[H._meet[a, b]] + H._rank[H._join[a, b]]
                       for a in range(n) for b in range(a + 1, n))

        L = [self._element_to_vertex_dict[x] for x in L]
        return all(H._rank[a] + H._rank[b] ==
                   H._rank[H._meet[a, b]] + H._rank[H._join[a, b]]
                   for a in L for b in range(n))

    def is_modular_element(self, x):
        r"""
        Return ``True`` if ``x`` is a modular element and ``False`` otherwise.

        INPUT:

        - ``x`` -- an element of the lattice

        An element `x` in a lattice `L` is *modular* if `x \leq b` implies

        .. MATH::

            x \vee (a \wedge b) = (x \vee a) \wedge b

        for every `a, b \in L`.

        .. SEEALSO::

            :meth:`is_modular` to check modularity for the full lattice or
            some set of elements

        EXAMPLES::

            sage: L = LatticePoset({1:[2,3],2:[4,5],3:[5,6],4:[7],5:[7],6:[7]})
            sage: L.is_modular()
            False
            sage: [L.is_modular_element(x) for x in L]
            [True, True, False, True, True, False, True]
        """
        return self.is_modular([x])

    def is_upper_semimodular(self):
        r"""
        Return ``True`` if the lattice is upper semimodular and
        ``False`` otherwise.

        A lattice is upper semimodular if for any `x` in the lattice that is
        covered by `y` and `z`, both `y` and `z` are covered by their join.

        .. SEEALSO::

            :meth:`is_modular` and :meth:`is_lower_semimodular`.

        See :wikipedia:`Semimodular_lattice`

        EXAMPLES::

            sage: L = posets.DiamondPoset(5)
            sage: L.is_upper_semimodular()
            True

            sage: L = posets.PentagonPoset()
            sage: L.is_upper_semimodular()
            False

            sage: L = posets.ChainPoset(6)
            sage: L.is_upper_semimodular()
            True

            sage: L = LatticePoset(posets.IntegerPartitions(4))
            sage: L.is_upper_semimodular()
            True

        ALGORITHM:

        Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1]_.
        """
        if not self.is_ranked():
            return False
        H = self._hasse_diagram
        n = H.order()
        return all(H._rank[a] + H._rank[b] >=
                   H._rank[H._meet[a, b]] + H._rank[H._join[a, b]]
                   for a in range(n) for b in range(a + 1, n))

    def is_lower_semimodular(self):
        r"""
        Return ``True`` if the lattice is lower semimodular and
        ``False`` otherwise.

        A lattice is lower semimodular if for any `x` in the lattice that covers
        `y` and `z`, both `y` and `z` cover their meet.

        .. SEEALSO::

            :meth:`is_modular` and :meth:`is_upper_semimodular`.

        See :wikipedia:`Semimodular_lattice`

        EXAMPLES::

            sage: L = posets.DiamondPoset(5)
            sage: L.is_lower_semimodular()
            True

            sage: L = posets.PentagonPoset()
            sage: L.is_lower_semimodular()
            False

            sage: L = posets.ChainPoset(6)
            sage: L.is_lower_semimodular()
            True

        ALGORITHM:

        Based on pp. 286-287 of Enumerative Combinatorics, Vol 1 [EnumComb1]_.
        """
        if not self.is_ranked():
            return False
        H = self._hasse_diagram
        n = H.order()
        return all(H._rank[a] + H._rank[b] <=
                   H._rank[H._meet[a,b]] + H._rank[H._join[a,b]]
                   for a in range(n) for b in range(a+1, n))

    def is_supersolvable(self):
        """
        Return ``True`` if ``self`` is a supersolvable lattice and
        ``False`` otherwise.

        A lattice `L` is *supersolvable* if there exists a maximal chain `C`
        such that every `x \in C` is a modular element in `L`.

        EXAMPLES::

            sage: L = posets.DiamondPoset(5)
            sage: L.is_supersolvable()
            True

            sage: L = posets.PentagonPoset()
            sage: L.is_supersolvable()
            False

            sage: L = posets.ChainPoset(6)
            sage: L.is_supersolvable()
            True

            sage: L = LatticePoset({1:[2,3],2:[4,5],3:[5,6],4:[7],5:[7],6:[7]})
            sage: L.is_supersolvable()
            True
            sage: L.is_modular()
            False

            sage: L = LatticePoset({0: [1, 2, 3, 4], 1: [5, 6, 7],
            ....:                   2: [5, 8, 9], 3: [6, 8, 10], 4: [7, 9, 10],
            ....:                   5: [11], 6: [11], 7: [11], 8: [11],
            ....:                   9: [11], 10: [11]})
            sage: L.is_supersolvable()
            False

        TESTS::

            sage: LatticePoset({}).is_supersolvable()
            True
        """
        from sage.misc.cachefunc import cached_function

        if not self.is_ranked():
            return False

        if self.cardinality() == 0:
            return True

        H = self._hasse_diagram
        height = self.height()
        n = H.order()
        cur = H.maximal_elements()[0]
        next_ = [H.neighbor_in_iterator(cur)]

        @cached_function
        def is_modular_elt(a):
            return all(H._rank[a] + H._rank[b] ==
                       H._rank[H._meet[a, b]] + H._rank[H._join[a, b]]
                       for b in range(n))

        if not is_modular_elt(cur):
            return False
        while len(next_) < height:
            try:
                cur = next(next_[-1])
            except StopIteration:
                next_.pop()
                if not next_:
                    return False
                continue
            if is_modular_elt(cur):
                next_.append(H.neighbor_in_iterator(cur))
        return True

    def vertical_decomposition(self, elements_only=False):
        r"""
        Return sublattices from the vertical decomposition of the lattice.

        Let `d_1, \ldots, d_n` be elements (excluding the top and bottom
        elements) comparable to every element of the lattice. Let `b`
        be the bottom element and `t` be the top element. This function
        returns either a list `d_1, \ldots, d_n`, or the list of
        intervals `[b, d_1], [d_1, d_2], \ldots, [d_{n-1}, d_n], [d_n,
        t]` as lattices.

        Informally said, this returns the lattice split into parts at
        every single-element "cutting point".

        INPUT:

        - ``elements_only`` - if ``True``, return the list of decomposing
          elements as defined above; if ``False`` (the default),
          return the list of sublattices so that the lattice is a
          vertical composition of them.

        .. SEEALSO::

            :meth:`is_vertically_decomposable`

        EXAMPLES:

        Number 6 is divided by 1, 2, and 3, and it divides 12, 18 and 36::

            sage: L = LatticePoset( ([1, 2, 3, 6, 12, 18, 36],
            ....:     attrcall("divides")) )
            sage: parts = L.vertical_decomposition()
            sage: [lat.list() for lat in parts]
            [[1, 2, 3, 6], [6, 12, 18, 36]]
            sage: L.vertical_decomposition(elements_only=True)
            [6]

        TESTS::

            sage: [Posets.ChainPoset(i).vertical_decomposition(elements_only=True)
            ....:     for i in range(5)]
            [[], [], [], [1], [1, 2]]
        """
        if self.cardinality() <= 2:
            if not elements_only:
                return [self]
            else:
                return []
        if elements_only:
            return [self[e] for e in
                    self._hasse_diagram.vertical_decomposition(return_list=True)]
        elms = ( [0] +
                 self._hasse_diagram.vertical_decomposition(return_list=True) +
                 [self.cardinality()-1] )
        n = len(elms)
        result = []
        for i in range(n-1):
            result.append(LatticePoset(
                self.subposet([self[e] for e in range(elms[i], elms[i+1]+1)])))
        return result

    def is_vertically_decomposable(self):
        r"""
        Return ``True`` if the lattice is vertically decomposable, and
        ``False`` otherwise.

        A lattice is vertically decomposable if it has an element that
        is comparable to all elements and is neither the bottom nor
        the top element.

        Informally said, a lattice is vertically decomposable if it
        can be seen as two lattices "glued" by unifying the top
        element of first lattice to the bottom element of second one.

        .. SEEALSO::

            :meth:`vertical_decomposition`

        EXAMPLES::

            sage: L = LatticePoset( ([1, 2, 3, 6, 12, 18, 36],
            ....:     attrcall("divides")) )
            sage: L.is_vertically_decomposable()
            True
            sage: Posets.TamariLattice(4).is_vertically_decomposable()
            False

        TESTS::

            sage: [Posets.ChainPoset(i).is_vertically_decomposable() for i in
            ....:     range(5)]
            [False, False, False, True, True]
        """
        # TODO: Make better example when compose_vertically() is done.
        return self._hasse_diagram.vertical_decomposition()

    def sublattice(self, elms):
        r"""
        Return the smallest sublattice containing elements on the given list.

        INPUT:

        - ``elms`` -- a list of elements of the lattice.

        EXAMPLES::

            sage: L=LatticePoset(( [], [[1,2],[1,17],[1,8],[2,3],[2,22],[2,5],[2,7],[17,22],[17,13],[8,7],[8,13],[3,16],[3,9],[22,16],[22,18],[22,10],[5,18],[5,14],[7,9],[7,14],[7,10],[13,10],[16,6],[16,19],[9,19],[18,6],[18,33],[14,33],[10,19],[10,33],[6,4],[19,4],[33,4]] ))
            sage: L.sublattice([14, 13, 22]).list()
            [1, 2, 8, 7, 14, 17, 13, 22, 10, 33]

            sage: L = Posets.BooleanLattice(3)
            sage: L.sublattice([3,5,6,7])
            Finite lattice containing 8 elements
        """
        gens_remaining = set(elms)
        current_set = set()

        # We add elements one by one in 'current_set'.
        #
        # When adding a point g to 'current_set', we add to 'gens_remaning' all
        # meet/join obtained from g and another point of 'current_set'
        while gens_remaining:
            g = gens_remaining.pop()
            if g in current_set:
                continue
            for x in current_set:
                gens_remaining.add(self.join(x,g))
                gens_remaining.add(self.meet(x,g))
            current_set.add(g)

        return LatticePoset(self.subposet(current_set))

    def maximal_sublattices(self):
        r"""
        Return maximal (proper) sublattices of the lattice.

        EXAMPLES::

            sage: L = LatticePoset(( [], [[1,2],[1,17],[1,8],[2,3],[2,22],
            ....:                         [2,5],[2,7],[17,22],[17,13],[8,7],
            ....:                         [8,13],[3,16],[3,9],[22,16],[22,18],
            ....:                         [22,10],[5,18],[5,14],[7,9],[7,14],
            ....:                         [7,10],[13,10],[16,6],[16,19],[9,19],
            ....:                         [18,6],[18,33],[14,33],[10,19],
            ....:                         [10,33],[6,4],[19,4],[33,4]] ))
            sage: maxs = L.maximal_sublattices()
            sage: len(maxs)
            7
            sage: sorted(maxs[0].list())
            [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 16, 18, 19, 22, 33]
        """
        n = self.cardinality()
        if n < 2:
            return []
        if n == 2:
            return [self.sublattice([self.bottom()]), self.sublattice([self.top()])]
        return [self.sublattice([self[x] for x in d]) for d in self._hasse_diagram.maximal_sublattices()]

    def frattini_sublattice(self):
        r"""
        Return the Frattini sublattice of the lattice.

        The Frattini sublattice `\Phi(L)` is the intersection of all
        proper maximal sublattices of `L`. It is also the set of
        "non-generators" - if the sublattice generated by set `S` of
        elements is whole lattice, then also `S \setminus \Phi(L)`
        generates whole lattice.

        EXAMPLES::

            sage: L = LatticePoset(( [], [[1,2],[1,17],[1,8],[2,3],[2,22],
            ....:                         [2,5],[2,7],[17,22],[17,13],[8,7],
            ....:                         [8,13],[3,16],[3,9],[22,16],[22,18],
            ....:                         [22,10],[5,18],[5,14],[7,9],[7,14],
            ....:                         [7,10],[13,10],[16,6],[16,19],[9,19],
            ....:                         [18,6],[18,33],[14,33],[10,19],
            ....:                         [10,33],[6,4],[19,4],[33,4]] ))
            sage: sorted(L.frattini_sublattice().list())
            [1, 2, 4, 10, 19, 22, 33]
        """
        return LatticePoset(self.subposet([self[x] for x in
                self._hasse_diagram.frattini_sublattice()]))

    def moebius_algebra(self, R):
        """
        Return the Möbius algebra of ``self`` over ``R``.

        EXAMPLES::

            sage: L = posets.BooleanLattice(4)
            sage: L.moebius_algebra(QQ)
            Moebius algebra of Finite lattice containing 16 elements over Rational Field
        """
        from sage.combinat.posets.moebius_algebra import MoebiusAlgebra
        return MoebiusAlgebra(R, self)

    def quantum_moebius_algebra(self, q=None):
        """
        Return the quantum Möbius algebra of ``self`` with parameter ``q``.

        INPUT:

        - ``q`` -- (optional) the deformation parameter `q`

        EXAMPLES::

            sage: L = posets.BooleanLattice(4)
            sage: L.quantum_moebius_algebra()
            Quantum Moebius algebra of Finite lattice containing 16 elements
             with q=q over Univariate Laurent Polynomial Ring in q over Integer Ring
        """
        from sage.combinat.posets.moebius_algebra import QuantumMoebiusAlgebra
        return QuantumMoebiusAlgebra(self, q)

    def is_dismantlable(self, certificate=False):
        r"""
        Return ``True`` if the lattice is dismantlable, and ``False``
        otherwise.

        An `n`-element lattice `L_n` is dismantlable if there is a sublattice
        chain `L_{n-1} \supset L_{n-2}, \supset \cdots, \supset L_0` so that
        every `L_i` is a sublattice of `L_{i+1}` with one element less, and
        `L_0` is the empty lattice. In other words, a dismantlable lattice
        can be reduced to empty lattice removing doubly irreducible
        element one by one.

        INPUT:

        - ``certificate`` (boolean) -- Whether to return a certificate.

          * If ``certificate = False`` (default), returns ``True`` or
            ``False`` accordingly.

          * If ``certificate = True``, returns:

            * ``(True, elms)`` when the lattice is dismantlable, where
              ``elms`` is elements listed in a possible removing order.

            * ``(False, crown)`` when the lattice is not dismantlable,
              where ``crown`` is a subposet of `2k` elements
              `a_1, \ldots, a_k, b_1, \ldots, b_k` with covering
              relations `a_i \lessdot b_i` and `a_i \lessdot b_{i+1}`
              for `i \in [1, \ldots, k-1]`, and `a_k \lessdot b_1`.

        EXAMPLES::

            sage: DL12 = LatticePoset((divisors(12), attrcall("divides")))
            sage: DL12.is_dismantlable()
            True
            sage: DL12.is_dismantlable(certificate=True)
            (True, [4, 2, 1, 3, 6, 12])

            sage: B3 = Posets.BooleanLattice(3)
            sage: B3.is_dismantlable()
            False
            sage: B3.is_dismantlable(certificate=True)
            (False, Finite poset containing 6 elements)

        Every planar lattice is dismantlable. Converse is not true::

            sage: L = LatticePoset( ([], [[0, 1], [0, 2], [0, 3], [0, 4],
            ....:                         [1, 7], [2, 6], [3, 5], [4, 5],
            ....:                         [4, 6], [4, 7], [5, 8], [6, 8],
            ....:                         [7, 8]]) )
            sage: L.is_dismantlable()
            True
            sage: L.is_planar()
            False

        TESTS::

            sage: Posets.ChainPoset(0).is_dismantlable()
            True
            sage: Posets.ChainPoset(1).is_dismantlable()
            True

            sage: L = LatticePoset(DiGraph('L@_?W?E?@CCO?A?@??_?O?Jw????C?'))
            sage: L.is_dismantlable()
            False
            sage: c = L.is_dismantlable(certificate=True)[1]
            sage: (3 in c, 12 in c, 9 in c)
            (True, False, True)
        """
        from sage.graphs.digraph import DiGraph
        from copy import copy

        H = copy(self._hasse_diagram)
        cert = []
        # Smallest lattice that is not dismantlable is the
        # Boolean lattice with 2^3=8 elements. Hence the limit 7.
        limit = 0 if certificate else 7

        while H.order() > limit:
            for e in H:
                i = H.in_degree(e)
                o = H.out_degree(e)
                if i < 2 and o < 2:
                    if certificate:
                        cert.append(e)
                    if i == 1 and o == 1:  # Remove inside the lattice
                        lower = H.neighbors_in(e)[0]
                        upper = H.neighbors_out(e)[0]
                        H.delete_vertex(e)
                        if not upper in H.depth_first_search(lower):
                            H.add_edge(lower, upper)
                    else:  # Remove the top or bottom element
                        H.delete_vertex(e)
                    break
            else:
                if not certificate:
                    return False
                k = 3
                while True:
                    crown = DiGraph({i: [k + i, k + (i + 1) % k]
                                     for i in range(k)})
                    sg = H.transitive_closure().subgraph_search(crown, True)
                    if sg:
                        elms = [self[e] for e in sg]
                        return (False, self.subposet(elms))
                    k += 1
        if not certificate:
            return True
        return (True, [self[e] for e in cert])

############################################################################

FiniteMeetSemilattice._dual_class = FiniteJoinSemilattice
FiniteJoinSemilattice._dual_class = FiniteMeetSemilattice
FiniteLatticePoset   ._dual_class = FiniteLatticePoset
